下列各种数据结构中属于线性结构的有()

以下数据结构中，（ ）是非线性数据结构。

对于顺序存储的长度为$N$的线性表，访问结点和增加结点的时间复杂度为：

在$N$个结点的顺序表中，算法的时间复杂度为O(1)的操作是：

若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用哪种存储方式最节省时间？

线性表若采用链式存储结构时，要求内存中可用存储单元的地址

在具有$N$个结点的单链表中，实现下列哪个操作，其算法的时间复杂度是$O(N)$？

某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用什么存储方式最节省运算时间？

若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用哪种存储方式最节省运算时间？

将线性表La和Lb头尾连接，要求时间复杂度为O(1)，且占用辅助空间尽量小。应该使用哪种结构？

线性表L在什么情况下适用于使用链式结构实现？

对于一个具有$N$个结点的单链表，在给定值为$x$的结点后插入一个新结点的时间复杂度为

链表不具有的特点是：

设h为不带头结点的单向链表。在h的头上插入一个新结点t的语句是：

采用多项式的非零项链式存储表示法，如果两个多项式的非零项分别为$N_1$和$N_2$个，最高项指数分别为$M_1$和$M_2$，则实现两个多项式相加的时间复杂度是：

将两个结点数都为$N$且都从小到大有序的单向链表合并成一个从小到大有序的单向链表，那么可能的最少比较次数是：

有六个元素以6、5、4、3、2、1的顺序进栈，问哪个不是合法的出栈序列？

若一个栈的入栈序列为1、2、3、…、$N$，输出序列的第一个元素是$i$，则第$j$个输出元素是：

若一个栈的入栈序列为1、2、3、…、$N$，其输出序列为$p_1$、$p_2$、$p_3$、…、$p_N$。若$p_1=N$，则$p_i$为：

令P代表入栈，O代表出栈。若利用堆栈将中缀表达式3*2+8/4转为后缀表达式，则相应的堆栈操作序列是：

若借助堆栈将中缀表达式a+b*c+(d*e+f)*g转换为后缀表达式，当读入f时，堆栈里的内容是什么（按堆栈自底向上顺序）？

设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4，则最后一个出栈的元素必定是：

表达式a*(b+c)-d的后缀表达式是：

从栈顶指针为ST的链栈中删除一个结点且用X保存被删结点的值，则执行：

若top为指向栈顶元素的指针，判定栈S（最多容纳m个元素）为空的条件是：

若采用带头、尾指针的单向链表表示一个堆栈，那么该堆栈的栈顶指针top应该如何设置？

利用大小为n的数组（下标从0到n-1）存储一个栈时，假定栈从数组另一头开始且top==n表示栈空，则向这个栈插入一个元素时，修改top指针应当执行：

为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是？

若已知一队列用单向链表表示，该单向链表的当前状态（含3个对象）是：1->2->3，其中x->y表示x的下一节点是y。此时，如果将对象4入队，然后队列头的对象出队，则单向链表的状态是：

某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a、b、c、d、e依次入此队列后再进行出队操作，则不可能得到的出队序列是：

若用大小为6的数组来实现循环队列，且当前front和rear的值分别为0和4。当从队列中删除两个元素，再加入两个元素后，front和rear的值分别为多少？

如果循环队列用大小为m的数组表示，且用队头指针front和队列元素个数size代替一般循环队列中的front和rear指针来表示队列的范围，那么这样的循环队列可以容纳的元素个数最多为：

设栈S和队列Q的初始状态均为空，元素{1, 2, 3, 4, 5, 6, 7}依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是{2, 5, 6, 4, 7, 3, 1}，则栈S的容量至少是：

给定一个堆栈的入栈序列为{ 1, 2, $\cdots$, $n$ }，出栈序列为{ $p_1$, $p_2$, $\cdots$, $p_n$ }。如果$p_2 = n$，则存在多少种不同的出栈序列？

采用多项式的非零项链式存储表示法，如果两个多项式的非零项分别为$N_1$和$N_2$个，最高项指数分别为$M_1$和$M_2$，则实现两个多项式相乘的时间复杂度是：

下列关于栈的叙述中，错误的是：

1. 采用非递归方式重写递归程序时必须使用栈
2. 函数调用时，系统要用栈保存必要的信息
3. 只要确定了入栈次序，即可确定出栈次序
4. 栈是一种受限的线性表，允许在其两端进行操作

适用于压缩存储稀疏矩阵的两种存储结构是：

已知指针ha和hb分别是两个单链表的头指针，下列算法将这两个链表首尾相连在一起，并形成一个循环链表（即ha的最后一个结点链接hb的第一个结点，hb的最后一个结点指向ha），返回ha作为该循环链表的头指针。请将该算法补充完整。

typedef struct node{
ElemType data;
    struct node *next;
}LNode;
LNode *merge(LNode *ha, LNode *hb) {
LNode *p=ha;
     if (ha==NULL || hb==NULL) {
cout<<”one or two link lists are empty!”<<endl;
          return NULL;
     }
     while ( p->next!=NULL )
           p=p->next;
     p->next=hb;
     while ( p->next!=NULL )
           p=p->next;
           __________
}

在一个不带头结点的非空链式队列中,假设f和r分别为队头和队尾指针,则插入s所指的结点运算是( )。

若栈$S_1$中保存整数，栈$S_2$中保存运算符，函数F()依次执行下述各步操作：

• （1）从$S_1$中依次弹出两个操作数a和b；
• （2）从$S_2$中弹出一个运算符op；
• （3）执行相应的运算b op a；
• （4）将运算结果压入$S_1$中。

假定$S_1$中的操作数依次是{ 5, 8, 3, 2 }（2在栈顶），$S_2$中的运算符依次是{ *, -, + }（+在栈顶）。调用3次F()后，$S_1$栈顶保存的值是：

现有队列 Q 与栈 S，初始时 Q 中的元素依次是{ 1, 2, 3, 4, 5, 6 }（1在队头），S 为空。若允许下列3种操作：（1）出队并输出出队元素；（2）出队并将出队元素入栈；（3）出栈并输出出栈元素，则不能得到的输出序列是：

设有一个 12$\times$12 的对称矩阵$M$，将其上三角部分的元素$m_{i,j}$（$1\le i\le j\le 12$）按行优先存入C语言的一维数组N中，元素$m_{6,6}$在N中的下标是：

稀疏矩阵采用三元组存储的时候，一般需要一个行逻辑链接的顺序表，用以指出每一行的第一个非零元素在三元组中的位置。用这个顺序表的主要目的是为了___。

对空栈 $S$ 进行 Push 和 Pop 操作，入栈序列为 a, b, c, d, e，经过 Push, Push, Pop, Push, Pop, Push, Push, Pop 操作后，得到的出栈序列是：

循环队列的引入，目的是为了克服( )。

链表 - 存储密度

链表的存储密度 ▁▁▁▁▁ 。

表达式3*2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（ ），其中^为乘幂 。

在作进栈运算时，应先判别栈是否(① )；在作退栈运算时应先判别栈是否(② )。当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为(③ )。

①: A. 空 B. 满 C. 上溢 D. 下溢

②: A. 空 B. 满 C. 上溢 D. 下溢

③: A. n-1 B. n C. n+1 D. n/2

设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是( )。

元素A,B,C,D依次入栈，出栈无限制，则以下（ ）是可能的出栈序列。

用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为( )。

循环队列的队满条件为 ( )。

栈和队列的共同点是（ ）。

已知初始为空的队列 Q 的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若 Q 的入队序列是 1、2、3、4、5，则不能得到的出队序列是：